import numpy as np
import pandas as pd
from collections import Counter, defaultdict
import string
import plotly.express as px
import plotly.offline as py
from typing import Dict
cyrillic_alphabet = set('абвгдеёжзийклмнопрстуфхцчшщъыьэюя')
ascii_alphabet = set(string.ascii_lowercase)
print(f'cyrillic_alphabet={sorted(list(cyrillic_alphabet))}')
print(f'ascii_alphabet={sorted(list(ascii_alphabet))}')
cyrillic_alphabet=['а', 'б', 'в', 'г', 'д', 'е', 'ж', 'з', 'и', 'й', 'к', 'л', 'м', 'н', 'о', 'п', 'р', 'с', 'т', 'у', 'ф', 'х', 'ц', 'ч', 'ш', 'щ', 'ъ', 'ы', 'ь', 'э', 'ю', 'я', 'ё'] ascii_alphabet=['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
def read_file(filename):
with open(filename, 'r') as fn:
return fn.read()
def clear_text(text, alphabet, add_space=True):
permitted_chars = alphabet
if add_space:
permitted_chars = set(alphabet) | {" "}
return ''.join(x for x in text.lower() if x in permitted_chars)
def count_n_grams(text, n=1):
counter = Counter()
for start in range(0, len(text) - n + 1):
counter.update([text[start : start+n]])
return counter
def read_corpus(filename, alphabet, n_gram_size=1, add_space=True):
text = read_file(filename)
text = clear_text(text, alphabet, add_space)
return count_n_grams(text, n_gram_size)
def corpus_to_df(corpus):
df = pd.DataFrame([dict(char=k, count=v) for k,v in corpus.items()])
total_num = float(sum(corpus.values()))
df['count'] /= total_num
return df.sort_values('char')
def generate_samples(filename, alphabet, min_len, max_len, number_of_samples, add_space=True):
sample = read_file(filename)
sample = [clear_text(x, alphabet, add_space) for x in sample.split('\n')]
sample = [x for x in sample if min_len <= len(x) <= max_len]
return np.random.choice(sample, number_of_samples)
def permutate(sample):
chars = list(set(sample))
original_chars = list(set(sample))
np.random.shuffle(chars)
permutation = {orig: to for orig, to in zip(original_chars, chars)}
# for orig, to in zip(original_chars, chars):
# print(f'replacing {orig} -> {to}')
return ''.join(permutation[c] for c in sample), permutation
def unpermutate(permutated_text, permutation):
inversed_index = {v:k for k,v in permutation.items()}
return ''.join(inversed_index[c] for c in permutated_text)
def freq_to_sorted_list(freq: Dict):
return sorted([(k,v) for k,v in freq.items()], key=lambda x: -x[-1])
def plot_accuracy(x, y, title, window):
fig = px.scatter(x=x, y=y, title=title,
labels={'x': 'length of sample', 'y': 'accuracy'})
sums, counts = defaultdict(float), defaultdict(int)
for xi, yi in zip(x, y):
x_key = xi // window * window
sums[x_key] += yi
counts[x_key] += 1
mean_x = sorted(sums.keys())
fig.add_scatter(x=mean_x, y=[sums[xi]/counts[xi] for xi in mean_x], name='mean line', opacity=0.7, )
return fig
print(f"Example of cleared text:\n\t{clear_text(read_file('WarAndPeace.txt'), cyrillic_alphabet)[:400]}")
wap_corpus = read_corpus('WarAndPeace.txt', cyrillic_alphabet)
fig = px.histogram(corpus_to_df(wap_corpus), x='char', y='count',
labels={'count':'char count'},
title='Chars distribution')
Example of cleared text: война и мир самый известный роман льва николаевича толстого как никакое другое произведение писателя отражает глубину его мироощущения и философииэта книга из разряда вечных потому что она обо всем о жизни и смерти о любви и чести о мужестве и героизме о славе и подвиге о войне и мирепервый том знакомит с высшим обществом россии века показаны взаимоотношения между родителями и детьми в семье ро
def try_decode_1gram(sample, corpus):
sample_freq = count_n_grams(sample, n=1)
sample_freq = freq_to_sorted_list(sample_freq)
corpus_freq = freq_to_sorted_list(corpus)
inverted_index = {}
for sc, cc in zip(sample_freq, corpus_freq):
from_c, _ = sc
to_c, _ = cc
inverted_index[from_c] = to_c
# print(f'encoding {from_c} -> {to_c}')
return ''.join(inverted_index[c] for c in sample)
def char_accuracy(s1, s2):
total = 0
equal = 0
for c1, c2 in zip(s1, s2):
total += 1
equal += c1 == c2
return 100.0 * equal / total
debug_output = False
x, y = [], []
samples = generate_samples('AnnaKarenina.txt', cyrillic_alphabet,
min_len=100, max_len=1000, number_of_samples=1000)
for sample in samples:
encoded, permutation = permutate(sample)
decoded = try_decode_1gram(encoded, wap_corpus)
acc = char_accuracy(sample, decoded)
x.append(len(sample))
y.append(acc)
if debug_output:
print (f'Original sample:\n\t{sample}\nDecoded sample:\n\t{decoded}')
print(f'Accuracy: {acc:0.1f}%')
fig = plot_accuracy(x=x, y=y, title='One-gram frequency analysis', window=10)
fig.show()
bigrams = read_corpus('WarAndPeace.txt', cyrillic_alphabet, n_gram_size=2, add_space=False)
sorted_cyrrilic_abc = sorted(list(cyrillic_alphabet))
bigrams_dist = np.zeros((len(sorted_cyrrilic_abc), len(sorted_cyrrilic_abc)))
for i, a in enumerate(sorted_cyrrilic_abc):
for j, b in enumerate(sorted_cyrrilic_abc):
bigrams_dist[i][j] = bigrams.get(a + b, 0.0)
print(f'Most common bigrams: {bigrams.most_common(10)}')
px.imshow(
bigrams_dist,
labels=dict(x="Second letter", y="First letter", color="Couccurance"),
x=sorted_cyrrilic_abc,
y=sorted_cyrrilic_abc,
title="Bigrams distribution"
)
Most common bigrams: [('то', 8663), ('ст', 6846), ('на', 6585), ('ов', 6487), ('ал', 5857), ('го', 5802), ('он', 5621), ('не', 5581), ('но', 5542), ('ко', 5494)]
most_frequent_bigrams = bigrams.most_common(100)
px.histogram(
x=[i[0] for i in most_frequent_bigrams],
y=[i[1] for i in most_frequent_bigrams],
labels={'x': 'bigrams', 'y': 'count'},
title='100 most common bigrams'
)
Поискав в Интеренете, про биграммный поиск пишут, что он просто аналогичен обычному. Тем не менее, у меня не сложилось четкого понимания, как декодировать с помощью биграмм. Очевидно, мы считаем частоту совстречаемости пар символов. Однако, дальше возникает вопрос, что делать.
Например, вот у нас в закодированной последовательности встречается такая комбинация: $$a_{t-1} a_t a_{t+1} a_{t+2}$$ Пусть мы знаем, что среди них $a_t a_{t+1}$ являются самой частой парой, и в соответствии с корпусом, мы им назначаем пару $b_t b_{t+1}$. Дальше возникает вопрос, как действовать. Например, пара $a_{t-1} a_t$ является следующей по частоте встречаемости, но ей соответсвует (по частоте в корпусе), пара $c_{t-1} c_{t}$, при чем $c_t \neq b_t$
Как поступать в таком случае?
В реализованном ниже примере используется следующий подход: мы выбираем наиболее вероятную пару из допустимых. То есть, в данном случае, мы наложим ограничение на выбор $c_{t} \equiv b_{t}$. Это позволяет однозначным образом декодировать. Недостатком является накапливание ошибки: если мы плохо декодировали самую вероятную пару, то дальше алгоритм уже не выправится.
class BiGramDecoder:
def __init__(self, alphabet, corpus_text):
self.alphabet = set(alphabet)
self.corpus_freq = count_n_grams(corpus_text, n=2)
self.corpus_freq_list = freq_to_sorted_list(self.corpus_freq)
self.already_processed = {}
def _decode(self, a, b):
if a in self.already_processed and b in self.already_processed:
return self.already_processed[a], self.already_processed[b]
elif a in self.already_processed:
best_p = -1.0
best_c = None
decoded_a = self.already_processed[a]
for c in self.alphabet - set(self.already_processed.values()):
if self.corpus_freq[decoded_a + c] > best_p:
best_p = self.corpus_freq[decoded_a + c]
best_c = c
self.already_processed[b] = c
return decoded_a, c
elif b in self.already_processed:
best_p = -1.0
best_c = None
decoded_b = self.already_processed[b]
for c in self.alphabet - set(self.already_processed.values()):
if self.corpus_freq[c + decoded_b] > best_p:
best_p = self.corpus_freq[c + decoded_b]
best_c = c
self.already_processed[a] = c
return c, decoded_b
else:
used = set(self.already_processed.values())
for seq, _ in self.corpus_freq_list:
c, d = seq
if c not in used and d not in used:
self.already_processed[a] = c
self.already_processed[b] = d
return c, d
def __call__(self, sample):
assert len(self.already_processed) == 0
sample_freq = freq_to_sorted_list(count_n_grams(sample, n=2))
letters_in_sample = len(set(sample))
for seq, cnt in sample_freq:
a, b = self._decode(seq[0], seq[1])
# print(f'{seq}[{cnt}] -> {a}{b}')
if len(self.already_processed) == letters_in_sample:
break
# print(self.already_processed)
# print(sample)
return ''.join(self.already_processed[c] for c in sample)
def reset(self):
self.already_processed = {}
debug_output = False
x, y = [], []
corpus_text = clear_text(read_file('WarAndPeace.txt'), cyrillic_alphabet, add_space=False)
decoder = BiGramDecoder(cyrillic_alphabet, corpus_text)
samples = generate_samples('AnnaKarenina.txt', cyrillic_alphabet, add_space=False,
min_len=200, max_len=2000, number_of_samples=1000)
for sample in samples:
encoded, permutation = permutate(sample)
decoder.reset()
decoded = decoder(encoded)
acc = char_accuracy(sample, decoded)
x.append(len(sample))
y.append(acc)
if debug_output:
print (f'Original sample:\n\t{sample}\nDecoded sample:\n\t{decoded}')
print(f'Accuracy: {acc:0.1f}%')
fig = plot_accuracy(x=x, y=y, title='Bi-gram frequency analysis', window=20)
fig.show()
Как видно, результат получился очень неустойчивым, и в среднем хуже, чем для униграмм.